BGA (Ball Grid Array) is one type of integrated circuit packages. The BGA has a high density of terminals, and therefore a merit of realizing miniaturization even for an integrated circuit having a large number of I/O terminals (pins) is obtained. On the other hand, because of the high density of the terminals, a space between the terminals may be narrow, and a problem occurs that wirings that may be led mutually scramble for the space between the terminals. Such a problem is more prominent as the density of the terminals is higher.
Incidentally, an operation of routing the wirings of the mutual integrated circuit packages on a printed circuit board (PCB) and a routing operation inside the integrated circuit packages are roughly divided into global routing and detailed routing. In the global routing, between which pins the respective wirings pass through, relative positional relations of the respective wirings, and the like are decided. In the detailed routing, on the basis of a result of the global routing, actual routing paths are decided. Hereinafter, the routing path created in the global routing is referred to as “global path”.
FIGS. 1A to 1C respectively show methods for the global routing in related art. In the same drawings, respective circles are pins on the BGA. As shown in FIG. 1A, in related art, a wiring area 200 is divided in horizontal and vertical directions in a grid manner while following a certain rule, and the global paths for the wirings are created along this grid. Hereinafter, it may be noted that in the drawings, circles 210, 211, 212, and 213 represent pins, and a grid point 220 with a small circle represents a grid point through which the global paths can pass.
FIG. 1A illustrates a routing example in which two lines of global paths 201 and 202 are created along this grid. However, in this example, no more global paths can be created along this grid. However, if a routing at an angle of 45 or 135 degrees is set for these global paths as shown in FIG. 1B, creation of a third line of a global path 203a indicated by the dotted line can be realized. (Global paths 201a and 202a)
Also, as shown in FIG. 1C, by chipping shapes of pins 210a, 211a, 212a, and 213a in conformity to a shape of the grid, the number of grid points 220 allowing the global routing can be increased. In this case, furthermore, as shown in FIG. 1D, it is also possible to create global paths 201c, 202c, 203c, and 204c corresponding to diagonal paths.
However, according to the method shown in FIGS. 1C and 1D, a problem takes place that a processing of chipping the pins is complicated. Also, the number of the grid points to be searched for is increased in accordance with increase in the number of allowable routings between the pins, and a problem arises that degradation of performance is conspicuous because of increase in memory consumption or calculation amount.
In this manner, the maximum number of wiring lines that can physically pass through between the terminals on the BGA varies depending on routing rules, places where the wirings pass, positional relations of surrounding pins, directions of wirings, and the like, and it is difficult to correctly associate the number of wiring lines that can pass with empty spaces.